package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         994,
		Discription: "全部橘子腐烂需要的时间",
		Level:       2,
		Labels: map[string]int{
			"拓扑排序":   1,
			"层序遍历": 1,
		},
	})
}

func OrangesRotting(grid [][]int) int {
	count := 0
	q := make([][2]int, 0)
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == 1 {
				count++
			} else if grid[i][j] == 2 {
				//记录初始的腐烂队列
				q = append(q, [2]int{i, j})
			}
		}
	}

	//没有新鲜的橘子，直接返回0
	if count == 0 {
		return 0
	}

	minutes := 0
	dirs := [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
	for len(q) != 0 {
		//每一轮层序遍历
		length := len(q)
		for k := 0; k < length; k++ {
			i := q[k][0]
			j := q[k][1]
            //向四周腐烂
			for _, dir := range dirs {
				x := i + dir[0]
				y := j + dir[1]
				if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
					continue
				}

				if grid[x][y] == 1 {
					q = append(q, [2]int{x, y})
					grid[x][y] = 2
					count--
				}
			}
		}

		minutes++
		if count == 0 {
			return minutes
		}
		q = q[length:]
	}

	return -1
}